package day230421;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/21 20:35
 * 求整数数组的最小不可组成和
 */
public class Solution {
    /**
     *	正数数组中的最小不可组成和
     *	输入：正数数组arr
     *	返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE; // 存储最小子集和, 即左区间
        int max = 0; // 存储最大子集和, 即右区间
        for(int item : arr) {
            min = Math.min(item, min);
            max += item;
        }
        // dp[i] 表示是否可能存在子集和为 i 的可能性
        boolean[] dp = new boolean[max + 1];
        dp[0] = true;
        for (int item : arr) {
            for (int i = max; i >= item; i--) {
                // 从后往前推
                if (dp[i-item]) {
                    // 如果存在, 则说明dp[i]存在
                    dp[i] = true;
                }
            }
        }
        // 计算结果, 返回最小不可组成和
        int res = max + 1;
        for (int i = min; i <= max; i++) {
            if (!dp[i]) {
                res = i;
                break;
            }
        }
        return res;
    }

    // 用于测试
    public static void main(String[] args) {
        int firstUnFormedNum = new Solution().getFirstUnFormedNum(new int[]{3, 2, 5});
        System.out.println(firstUnFormedNum);
    }
}
